package com.heima.leetcode.datastructure.binarytree;

import com.heima.datastructure.binarytree.TreeNode;

import java.util.LinkedList;

/**
 * <strong>逆波兰表达式（RPN，后缀表达式）转成表达式树</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/8 20:48
 */
public class RPNToExpressionTree {
    // 一、后缀表达式：     中缀表达式：      前缀表达式
    //     ab-c*           (a-b)*c          *-abc
    // 二、表达式树：很明显，表达式树的后序遍历的结果就是后缀表达式。中序遍历的结果就是中缀表达式（不带括号）。先序遍历的结果就是前缀表达式
    //         *
    //        / \
    //       -   c
    //      / \
    //     a   b
    // 三、所需栈：泛型为表达式树节点类
    //    |    |
    //    |    |
    //    |    |
    //    |    |
    //    |    |
    // 四、后缀表达式转表达式树步骤：（默认后缀表达式都是正确的）
    //     1、遍历后缀表达式，如果遇到数字，则建立节点压入栈中
    //     2、如果遇到运算符，则弹出第一个数字或者运算符节点，作为运算符的左子节点，弹出第二个数字或者运算符节点，作为运算符的右子节点
    //     3、建立好运算符的树节点后，再把建立好的运算符节点压入到栈中
    //     4、一直重复以上操作，直到遍历结束，栈中肯定还有一个运算符节点，弹出该节点返回
    public static TreeNode<String> constructExpressionTree(String[] tokens){
        LinkedList<TreeNode<String>> stack = new LinkedList<>();
        for (String token : tokens) {
            switch (token){
                case "+","-","*","/" -> {
                    TreeNode<String> node = new TreeNode<>(token);
                    node.right = stack.pop();
                    node.left = stack.pop();
                    stack.push(node);
                }
                default -> stack.push(new TreeNode<>(token));
            }
        }
        return stack.pop();
    }
}
